Evaluating%2C combining and generalizing recommendations with prerequisites.

Optimizing joins in a map%2Dreduce environment.
Implementations of map-reduce are being used to perform many operations on very large data. We examine strategies for joining several relations in the map-reduce environment. Our new approach begins by identifying the “map-key, ” the set of attributes that identify the Reduce process to which a Map process must send a particular tuple. Each attribute of the map-key gets a “share, ” which is the number of buckets into which its values are hashed, to form a component of the identifier of a Reduce process. Relations have their tuples replicated in limited fashion, the degree of replication depending on the shares for those map-key attributes that are missing from their schema. We study the problem of optimizing the shares, given a fixed number of Reduce processes. An algorithm for detecting and fixing problems where a variable is mistakenly included in the map-key is given. Then, we consider two important special cases: chain joins and star joins. In each case we are able to determine the mapkey and determine the shares that yield the least replication. While the method we propose is not always superior to the conventional way of using map-reduce to implement joins, there are some important cases involving large-scale data where our method wins, including: (1) analytic queries in which a very large fact table is joined with smaller dimension tables, and (2) queries involving paths through graphs with high out-degree, such as the Web or a social network.
Foundations of Uncertain%2DData Integration.
There has been considerable past work studying data integration and uncertain data in isolation. We develop the foundations for local-as-view (LAV) data integration when the sources being integrated are uncertain. We motivate two distinct settings for uncertain-data integration. We then define containment of uncertain databases in these settings, which allows us to express uncertain sources as views over a virtual mediated uncertain database. Next, we define consistency of a set of uncertain sources and show intractability of consistency-checking. We identify an interesting special case for which consistency-checking is polynomial. Finally, the notion of certain answers from traditional LAV data integration does not generalize to the uncertain setting, so we define a corresponding notion of correct answers. 1.
Schema Design for Uncertain Databases.
We address schema design in uncertain databases. Since uncertain data is relational in nature, decomposition becomes a key issue in design. Decomposition relies on dependency theory, and primarily on functional dependencies. We study the theory of functional dependencies (FDs) for uncertain relations. We define several kinds of horizontal FDs and vertical FDs, each of which is consistent with conventional FDs when an uncertain relation doesn’t contain any uncertainty. In addition to standard forms of decompositions allowed by ordinary relations, our FDs allow more complex decompositions specific to uncertain data. We show how our theory of FDs can be used for lossless decomposition of uncertain relations. We then present algorithms and complexity results for three fundamental problems with respect to FDs over ordinary and uncertain relations: (1) Testing whether a relation instance satisfies an FD; (2) Finding all FDs satisfied by a relation instance; and (3) Inferring all FDs that hold in the result of a query over uncertain relations with FDs. We also give a sound and complete axiomatization of horizontal and vertical FDs. We look at keys as a special case of FDs. Finally, we briefly consider uncertain data that contains confidence values. 
Viewpoint %2D Advising students for success.
03/2009 vol.52 no.03 cacm.acm.oRG ReBooteD! Being human in the Digital age
Using views to generate efficient evaluation plans for queries.

Gradiance On%2DLine Accelerated Learning.

The Lowell database research self%2Dassessment.

In memory of Seymour Ginsburg 1928 %2D 2004.

A Survey of New Directions in Database System.

Improving the Efficiency of Database%2DSystem Teaching.

The Lowell Report.
During the last decade many data integration systems characterized by a classical wrapper/mediator architecture [1] based on a Global Virtual Schema (Global Virtual View- GVV) have been proposed. The data sources store data, while the GVV provides a reconciled, integrated, and virtual view of the underlying sources. Each mediator system proposed (see [2] for a survey) contribute to the state of the art advancement by focusing on one or more challenge of the data integration problem, ranging from syntactical and semantic heterogeneities. At present, solving heterogeneities is a partially manual task, requiring a great amount of customization for data reconciliation and for writing specific not-reusable programming code. The last Lowell Report [3] has provided the guidelines for the definition of a public benchmark for data integration problems, called THALIA (Test
The Lowell Database Research Self Assessment

The Lowell Database Research Self Assessment

Querying websites using compact skeletons.

Minimizing View Sets without Losing Query%2DAnswering Power.
The problem of answering queries using views has been studied extensively due to its relevance in a wide variety of data-management applications. In these applications, we often need to select a subset of views to maintain due to limited resources. In this paper, we show that traditional query containment is not a good basis for deciding whether or not a view should be selected. Instead, we should minimize the view set without losing its query-answering power. To formalize this notion, we first introduce the concept of &#034;p-containment.&#034; That is, a view set V is p-contained in another view set W, if W can answer all the queries that can be answered by V. We show that p-containment and the traditional query containment are not related. We then discuss how to minimize a view set while retaining its query-answering power. We develop the idea further by considering p-containment of two view sets with respect to a given set of queries, and consider their relationship in terms o...
Querying Websites Using Compact Skeletons.

Generating Efficient Plans for Queries Using Views.
We study the problem of generating efficient, equivalent rewritings using views to compute the answer to a query. We take the closed-world assumption, in which views are materialized from base relations, rather than views describing sources in terms of abstract predicates, as is common when the open-world assumption is used. In the closedworld model, there can be an infinite number of different rewritings that compute the same answer, yet have quite different performance. Query optimizers take a logical plan (a rewriting of the query) as an input, and generate efficient physical plans to compute the answer. Thus our goal is to generate a small subset of the possible logical plans without missing an optimal physical plan.
Finding Interesting Associations without Support Pruning.
Abstract Association-rule mining has heretofore relied on the condition of high support to do its work efficiently. In particular, the well-known a-priori algorithm is only effective when the only rules of interest are relationships that occur very frequently. However, there are a number of applications, such as data mining, identification of similar web documents, clustering, and collaborative filtering, where the rules of interest have comparatively few instances in the data. In these cases, we must look for highly correlated items, or possibly even causal relationships between infrequent items. We develop a family of algorithms for solving this problem, employing a combination of random sampling and hashing techniques. We provide analysis of the algorithms developed, and conduct experiments on real and synthetic data to obtain a comparative performance analysis.
Introduction to automata theory%2C languages%2C and computation%2C 2nd edition.

Database System Implementation
We propose the use of semi-automatic methods for the translation of abstract database programs into efficient lower level user-defined primitives. We present a type transformation model for use in defining and facilitating the query translation and optimization process. We discuss how this model can be used also as a framework for schema evolution and data restructuring. 1 Introduction  Current database management systems, such as systems based on the relational model, lack the expressive power to support complex queries in a high level language and typically provide limited variety in their data structures. The limitation on the expressive power of the high level languages in these systems is commonly circumvented by embedding query languages in more expressive conventional programming languages. The disadvantage of this approach is that it forces the database designer to express his/her conceptual model in terms of two different semantic models. Additionally, for programming language...
A Survey of Association%2DRule Mining.
Discovering association rules is a well-established problem in the field of data mining, with many existing solutions. In later years, several methods have been proposed for mining rules from sequential and temporal data. This paper presents a novel technique based on genetic programming and specialized pattern matching hardware. The advantages of this method are its flexibility and adaptability, and its ability to produce intelligible rules of considerable complexity.
Finding Interesting Associations without Support Pruning.
Abstract Association-rule mining has heretofore relied on the condition of high support to do its work efficiently. In particular, the well-known a-priori algorithm is only effective when the only rules of interest are relationships that occur very frequently. However, there are a number of applications, such as data mining, identification of similar web documents, clustering, and collaborative filtering, where the rules of interest have comparatively few instances in the data. In these cases, we must look for highly correlated items, or possibly even causal relationships between infrequent items. We develop a family of algorithms for solving this problem, employing a combination of random sampling and hashing techniques. We provide analysis of the algorithms developed, and conduct experiments on real and synthetic data to obtain a comparative performance analysis.
Scalable Techniques for Mining Causal Structures.
Mining for association rules in market basket data has proved a fruitful area of research. Measures such as conditional probability (confidence) and correlation have been used to infer rules of the form &#034;the existence of item A implies the existence of item B.&#034; However, such rules indicate only a statistical relationship between  A and B. They do not specify the nature of the relationship: whether the presence of A causes the presence of B, or the converse, or some other attribute or phenomenon causes both to appear together. In applications, knowing such causal relationships is extremely useful for enhancing understanding and effecting change. While distinguishing causality from correlation is a truly difficult problem, recent work in statistics and Bayesian learning provide some avenues of attack. In these fields, the goal has generally been to learn complete causal models, which are essentially impossible to learn in large-scale data mining applications with a large number of variab...
Information integration using logical views.
Abstract. A number of ideas concerning information-integration tools can be thought of as constructing answers to queries using views that represent the capabilities of information sources. We review the formal basis of these techniques, which are closely related to containment algo-rithms for conjunctive queries and/or Datalog programs. Then we com-pare the approaches taken by AT&amp;T Labs &#039; &amp;quot;Information Manifold &amp;quot; and the Stanford &amp;quot;Tsimmis &amp;quot; project in these terms. 1 Theoretical Background Before addressing information-integration issues, let us review some of the basic ideas concerning conjunctive queries, Datalog programs, and their containment. To begin, we use the logical rule notation from [Ull88]. Example 1. The following: p(X,Z):- a(X,Y)  &amp; a(Y,Z). is a rule that talks about a, an EDB predicate (&amp;quot;Extensional DataBase, &amp;quot; or stored relation), and p, an IDB predicate (&amp;quot;Intensional DataBase, &amp;quot; or predicate whose relation is constructed by rules). In this and several other examples, it is useful to think of a as an &amp;quot;arc &amp;quot; predicate defining a graph, while other predicates define certain structures that might exist in the graph. That is, a(X, Y) means there is an arc from node X to node Y. In this case, the rule says &amp;quot;p(X, Z) is true if there is an arc from node X to node Y and also an arc from Y to Z.&amp;quot; That is, p represents paths of length 2. In general, there is one atom, the head, on the left of the &amp;quot;if &amp;quot; sign,:- and zero of more atoms, called subgoals, on the right side (the body). The head always has an IDB predicate; the subgoals can have IDB or EDB predicates. Thus, here p(X, Z) is the head, while a(X, Y) and a(Y, Z) are subgoals. We assume that each variable appearing in the head also appears somewhere in the body. This &amp;quot;safety &amp;quot; requirement assures that when we use a rule, we are not left with undefined variables in the head when we try to infer a fact about the head&#039;s predicate. We also assume that atoms consist of a predicate and zero or more arguments. An argument can be either a variable or a constant. However, we exclude function symbols from arguments.
Optimizing Large Join Queries in Mediation Systems.
. In data integration systems, queries posed to a mediator need to be translated into a sequence of queries to the underlying data sources. In a heterogeneous environment, with sources of diverse and limited query capabilities, not all the translations are feasible. In this paper, we study the problem of finding feasible and efficient query plans for mediator systems. We consider conjunctive queries on mediators and model the source capabilities through attribute-binding adornments. We use a simple cost model that focuses on the major costs in mediation systems, those involved with sending queries to sources and getting answers back. Under this metric, we develop two algorithms for source query sequencing -- one based on a simple greedy strategy and another based on a partitioning scheme. The first algorithm produces optimal plans in some scenarios, and we show a linear bound on its worst case performance when it misses optimal plans. The second algorithm generates optimal plans in mor...
The MIDAS Data%2DMining Project at Stanford.

Some Advances in Data%2DMining Techniques %28Abstract%29.

Computing Capabilities of Mediators.
Existing data-integration systems based on the mediation architecture employ avariety of mechanisms to describe the query-processing capabilities of sources. However, these systems do not compute the capabilities of the mediators based on the capabilities of the sources they integrate. In this paper, we propose a framework to capture a rich variety of query-processing capabilities of data sources and mediators. We present algorithms to compute the set of supported queries of a mediator, based on the capability limitations of its sources. Our algorithms take into consideration a variety of query-processing techniques employed by mediators to enhance the set of supported queries.
Answering Queries Using Limited External Query Processors.
When answering queries using external information sources, their contents can be described by views. To answer a query, we must rewrite it using the set of views presented by the sources. When the external information sources also have the ability to answer some (perhaps limited) sets of queries that require performing operations on their data, the set of views presented by the source may be infinite (albeit encoded in some finite fashion). Previous work on answering queries using views has only considered the case where the set of views is finite. In order to exploit the ability of information sources to answer more complex queries, we consider the problem of answering conjunctive queries using infinite sets of conjunctive views. Our first result is that an infinite set of conjunctive views can be partitioned into a finite number of equivalence classes, such that picking one view from every nonempty class is sufficient to determine whether the query can be answered using the views. Se...
Query Flocks A Generalization of Association%2DRule Mining.
Association-rule mining has proved a highly successful technique for extracting useful information from very large databases. This success is attributed not only to the appropriateness of the objectives, but to the fact that a number of new query-optimization ideas, such as the “a-priori ” trick, make association-rule mining run much faster than might be expected. In this paper we see that the same tricks can be extended to a much more general context, allowing efficient mining of very large databases for many different kinds of patterns. The general idea, called “query flocks,” is a generate-and-test model for data-mining problems. We show how the idea can be used either in a general-purpose mining system or in a next generation of conventional query optimizers. 1
Capability Based Mediation in TSIMMIS.
Introduction  The TSIMMIS system [1] integrates data from multiple heterogeneous sources and provides users with seamless integrated views of the data. It translates a user query on the integrated views into a set of source queries and postprocessing steps that compute the answer to the user query from the results of the source queries. TSIMMIS uses a  mediation architecture [11] to accomplish this (Figure 1). User Source 1 Source 2 Source N  Mediator Figure 1: The TSIMMIS Architecture Many other data integration systems like Garlic [2, 9] and Information Manifold [4] employ a similar architecture. One of the distinguishing features of TSIMMIS is its use of a semi-structured data model (called the Object Exchange Model or OEM [7]) for dealing with the heterogeneity of the data sources. In particular, it employs source wrappers [3] that provide a uniform OEM interface to the mediator. In SIGMO
Computing Iceberg Queries Efficiently.
Many applications compute aggregate functions...
Scalable Techniques for Mining Causal Structures.
Mining for association rules in market basket data has proved a fruitful area of research. Measures such as conditional probability (confidence) and correlation have been used to infer rules of the form &#034;the existence of item A implies the existence of item B.&#034; However, such rules indicate only a statistical relationship between  A and B. They do not specify the nature of the relationship: whether the presence of A causes the presence of B, or the converse, or some other attribute or phenomenon causes both to appear together. In applications, knowing such causal relationships is extremely useful for enhancing understanding and effecting change. While distinguishing causality from correlation is a truly difficult problem, recent work in statistics and Bayesian learning provide some avenues of attack. In these fields, the goal has generally been to learn complete causal models, which are essentially impossible to learn in large-scale data mining applications with a large number of variab...
The Asilomar Report on Database Research

Reminiscences on Influential Papers.

The Asilomar Report on Database Research.

A First Course in Database Systems.

Index Selection for OLAP.
On-line analytical processing (OLAP) is a recent and important application of database systems. Typically, OLAP data is presented as a multidimensional &#034;data cube.&#034; OLAP queries are complex and can take many hours or even days to run, if executed directly on the raw data. The most common method of reducing execution time is to precompute some of the queries into summary tables (subcubes of the data cube) and then to build indexes on these summary tables. In most commercial OLAP systems today, the summary tables that are to be precomputed are picked first, followed by the selection of the appropriate indexes on them. A trial-and-error approach is used to divide the space available between the summary tables and the indexes. This two-step process can perform very poorly. Since both summary tables and indexes consume the same resource -- space -- their selection should be done together for the most efficient use of space. In this paper, we give algorithms that automate the selection of summary tables and indexes. In particular, we present a family of algorithms of increasing time complexities, and prove strong performance bounds for them. The algorithms with higher complexities have better performance bounds. However, the increase in the performance bound is diminishing, and we show that an algorithm of moderate complexity can perform fairly close to the optimal.
Representative Objects Concise Representations of Semistructured
In this paper we introduce the representative object, which uncovers the inherent schema(s) in semistructured, hierarchical data sources and provides a concise description of the structure of the data. Semistructured data, unlike data stored in typical relational or object-oriented databases, does not have fixed schema that is known in advance and stored separately from the data. Withthe rapid growth of the World Wide Web, semistructured hierarchical data sources are becoming widely available to the casual user. The lack of external schema information currently makes browsing and querying these data sources inefficient at best, and impossible at worst. We show how representative objects make schema discovery efficient and facilitate the generation of meaningful queries over the data. 1. Introduction The goal of this paper is to present a tool, the &#034;representative object,&#034; that facilitates querying and browsing of semistructured, hierarchical information, such as that found on the web...
Information Integration Using Logical Views.
Abstract. A number of ideas concerning information-integration tools can be thought of as constructing answers to queries using views that represent the capabilities of information sources. We review the formal basis of these techniques, which are closely related to containment algo-rithms for conjunctive queries and/or Datalog programs. Then we com-pare the approaches taken by AT&amp;T Labs &#039; &amp;quot;Information Manifold &amp;quot; and the Stanford &amp;quot;Tsimmis &amp;quot; project in these terms. 1 Theoretical Background Before addressing information-integration issues, let us review some of the basic ideas concerning conjunctive queries, Datalog programs, and their containment. To begin, we use the logical rule notation from [Ull88]. Example 1. The following: p(X,Z):- a(X,Y)  &amp; a(Y,Z). is a rule that talks about a, an EDB predicate (&amp;quot;Extensional DataBase, &amp;quot; or stored relation), and p, an IDB predicate (&amp;quot;Intensional DataBase, &amp;quot; or predicate whose relation is constructed by rules). In this and several other examples, it is useful to think of a as an &amp;quot;arc &amp;quot; predicate defining a graph, while other predicates define certain structures that might exist in the graph. That is, a(X, Y) means there is an arc from node X to node Y. In this case, the rule says &amp;quot;p(X, Z) is true if there is an arc from node X to node Y and also an arc from Y to Z.&amp;quot; That is, p represents paths of length 2. In general, there is one atom, the head, on the left of the &amp;quot;if &amp;quot; sign,:- and zero of more atoms, called subgoals, on the right side (the body). The head always has an IDB predicate; the subgoals can have IDB or EDB predicates. Thus, here p(X, Z) is the head, while a(X, Y) and a(Y, Z) are subgoals. We assume that each variable appearing in the head also appears somewhere in the body. This &amp;quot;safety &amp;quot; requirement assures that when we use a rule, we are not left with undefined variables in the head when we try to infer a fact about the head&#039;s predicate. We also assume that atoms consist of a predicate and zero or more arguments. An argument can be either a variable or a constant. However, we exclude function symbols from arguments.
Dynamic Itemset Counting and Implication Rules for Market Basket Data.
We consider the problem of analyzing market-basket data and present several important contributions. First, we present a new algorithm for finding large itemsets which uses fewer passes over the data than classic algorithms, and yet uses fewer candidate itemsets than methods based on sampling. We investigate the idea of item reordering, which can improve the low-level efficiency of the algorithm. Second, we present a new way of generating &#034;implication rules,&#034; which are normalized based on both the antecedent and the consequent and are truly implications (not simply a measure of co-occurrence), and we show how they produce more intuitive results than other methods. Finally, we show how different characteristics of real data, as opposed to synthetic data, can dramatically affect the performance of the system and the form of the results.  1 Introduction  Within the area of data mining, the problem of deriving associations from data has recently received a great deal of attention. The prob...
The TSIMMIS Approach to Mediation Data Models and Languages.
TSIMMIS --- The Stanford-IBM Manager of Multiple Information Sources --- is a system for integrating information. It offers a data model and a common query language that are designed to support the combining of information from many different sources. It also offers tools for generating automatically the components that are needed to build systems for integrating information. In this paper we shall discuss the principal architectural features and their rationale. 1. Introduction  In this first section we introduce the core concept of mediators, which the Tsimmis system implements. Section 2 discusses the components of Tsimmis, and Section 3 discusses the OEM data model used by Tsimmis. Section 4 introduces the mediator-specification language MSL, while in Section 5 we learn how it is used to generate mediators and other components automatically. Finally, in Section 6 we consider another language, LOREL, based on the OEM data model. It is the Tsimmis end-user&#039;s query language as well as...
The TSIMMIS Approach to Mediation Data Models and Languages.
TSIMMIS --- The Stanford-IBM Manager of Multiple Information Sources --- is a system for integrating information. It offers a data model and a common query language that are designed to support the combining of information from many different sources. It also offers tools for generating automatically the components that are needed to build systems for integrating information. In this paper we shall discuss the principal architectural features and their rationale. 1. Introduction  In this first section we introduce the core concept of mediators, which the Tsimmis system implements. Section 2 discusses the components of Tsimmis, and Section 3 discusses the OEM data model used by Tsimmis. Section 4 introduces the mediator-specification language MSL, while in Section 5 we learn how it is used to generate mediators and other components automatically. Finally, in Section 6 we consider another language, LOREL, based on the OEM data model. It is the Tsimmis end-user&#039;s query language as well as...
Querying Semistructured Heterogeneous Information.
. Semistructured data has no absolute schema fixed in advance and its structure may be irregular or incomplete. Such data commonly arises in sources that do not impose a rigid structure (such as the World-Wide Web) and when data is combined from several heterogeneous sources. Data models and query languages designed for well structured data are inappropriate in such environments. Starting with a &#034;lightweight&#034; object model adopted for the TSIMMIS project at Stanford, in this paper we describe a query language and object repository designed specifically for semistructured data. Our language provides meaningful query results in cases where conventional models and languages do not: when some data is absent, when data does not have regular structure, when similar concepts are represented using different types, when heterogeneous sets are present, and when object structure is not fully known. This paper motivates the key concepts behind our approach, describes the language through a series o...
Mediator Languages %2D a Proposal for a Standard.
types (with methods) ffl Exchange of Meta-data In addition, early on in the Maryland meeting, it was decided that the following areas should also be discussed: ffl Exchange format for the data. ffl Communication protocol, including session control.   2.3 Alternative Approaches  Since the primary reason for wanting a core language is to facilitate the exchange of data, the immediate question is why not adopt one of the many existing standard data formats, e.g., ASN.1 [ISO1987], that have been developed for precisely this purpose. A simple request language would be needed to specify requests for data in this format. The problem with this solution is that most data sources do not simply dump all their data into some prescribed format; they usually respond to some request that describes what data is requested. Even if it were possible to obtain all this data, there may be problems of efficiency, and usability of this data. It is the language in which the requests are formulated -- the quer...
The Database Approach to Knowledge Represention.
The database theory community, centered around the PODS (Principles of Database Systems) conference has had a long-term interest in logic as a way to represent &#034;data,&#034; &#034;information,&#034; and &#034;knowledge&#034; (take your pick on the term --- it boils down to facts or atoms and rules, usually Horn clauses). The approach of this community has been &#034;slow and steady,&#034; preferring to build up carefully from simple special cases to more general ideas, always paying attention to how efficiently we can process queries and perform other operations on the facts and rules. A powerful theory has developed, and it is beginning to have some impact on applications, especially information-integration engines.  Datalog  The term Datalog has been coined to refer to Prolog-like rules without function symbols, treated as a logic program. Unlike Prolog, however, the conventional leastfixed -point semantics of the rules is used whenever possible.   Example 1: The rules for ancestors can be written as the following Data...
MedMaker A Mediation System Based on Declarative Specifications.
Mediators are used for integration of heterogeneous information sources. We present a system for declaratively specifying mediators. It is targeted for integration of sources with unstructured or semi-structured data and/or sources with changing schemas. We illustrate the main features of the Mediator Specification Language (MSL), show how they facilitate integration, and describe the implementation of the system that interprets the MSL specifications. 
Efficient Implementation of Data Cubes Via Materialized Views.

Deductive Databases Challenges

Answering Queries Using Limited External Processors.

Integrating Information by Outerjoins and Full Disjunctions.
) Anand Rajaraman Jeffrey D. Ullman  Department of Computer Science Stanford University  --anand, ullman@cs.stanford.edu Abstract  Our motivation is the piecing together of tidbits of information found on the &#034;web&#034; into a usable information structure. The problem is related to that of computing the natural outerjoin of many relations in a way that preserves all possible connections among facts. Such a computation has been termed a &#034;full disjunction&#034; by Galindo-Legaria. We are thus led to ask the question of when a full disjunction can be computed by some sequence of natural outerjoins. The answer involves a concept of from Fagin [1983] called &#034;fl-acyclic hypergraphs. &#034; We prove that there is a natural outerjoin sequence producing the full disjunction if and only if the set of relation schemes forms a connected, fl-acyclic  hypergraph.  I. Motivation  Let us imagine we are constructing an information resource that accepts queries about university information. We gather our information f...
The TSIMMIS Database Integration Project.

Implementing Data Cubes Efficiently.
Decision support applications involve complex queries on very large databases. Since response times should be small, query optimization is critical. Users typically view the data as multidimensional data cubes. Each cell of the data cube is a view consisting of an aggregation of interest, like total sales. The values of many of these cells are dependent on the values of other cells in the data cube. A common and powerful query optimization technique is to materialize some or all of these cells rather than compute them from raw data each time. Commercial systems differ mainly in their approach to materializing the data cube. In this paper, we investigate the issue of which cells (views) to materialize when it is too expensive to materialize all views. A lattice framework is used to express dependencies among views. We then present greedy algorithms that work off this lattice and determine a good set of views to materialize. The greedy algorithm performs within a small constant factor of...
LORE A Lightweight Object REpository for Semistructured Data.
The number of information sources accessible electronically is growing rapidly. Many of these sources store and export unstructured data in addition to or instead of structured data. In most cases, however, the unstructured data is not entirely devoid of structure, i.e., the data is semistructured. We consider data to be semistructured when there is no schema xed or known in advance and when the data may be incomplete or irregular. For example, HTML les on the World-Wide Web usually contain some structure, but often the data is irregular or incomplete. In addition, data integrated from multiple, heterogeneous information sources often is semistructured. Storing and querying semistructured data poses considerably di erent problems and requirements than
Moving Database Theory into Database Practice.

Database Research Achievements and Opportunities Into the 21st Century.
this paper reports on our findings.
A Query Translation Scheme for Rapid Implementation of Wrappers.
Wrappers provide access to heterogeneous information sources by converting application queries into source specific queries or commands. In this paper we present a wrapper implementation toolkit that facilitates rapid development of wrappers. We focus on the query translation component of the toolkit, called the converter. The converter takes as input a Query Description and Translation Language (QDTL) description of the queries that can be processed by the underlying source. Based on this description the converter decides if an application query is (a) directly supported, i.e., it can be translated to a query of the underlying system following instructions in the QDTL description; (b) logically supported, i.e., logically equivalent to a directly supported query; (c) indirectly supported, i.e., it can be computed by applying a filter,  automatically generated by the converter, to the result of a directly supported query. 1 Introduction  A wrapper or translator [C  +  94, PGMW95] is a s...
Querying Semistructured Heterogeneous Information.
. Semistructured data has no absolute schema fixed in advance and its structure may be irregular or incomplete. Such data commonly arises in sources that do not impose a rigid structure (such as the World-Wide Web) and when data is combined from several heterogeneous sources. Data models and query languages designed for well structured data are inappropriate in such environments. Starting with a &#034;lightweight&#034; object model adopted for the TSIMMIS project at Stanford, in this paper we describe a query language and object repository designed specifically for semistructured data. Our language provides meaningful query results in cases where conventional models and languages do not: when some data is absent, when data does not have regular structure, when similar concepts are represented using different types, when heterogeneous sets are present, and when object structure is not fully known. This paper motivates the key concepts behind our approach, describes the language through a series o...
A Version Numbering Scheme with a Useful Lexicographical Order.
We describe a numbering scheme for versions with alternatives that has a useful lexicographical ordering. The version hierarchy is a tree. By inspection of the version numbers, we can easily determine whether one version is an ancestor of another. If so, we can determine the version sequence between these two versions. If not, we can determine the most recent common ancestor to these two versions (i.e., the least upper bound, lub). Sorting the version numbers lexicographically results in a version being followed by all descendants and preceded by all its ancestors. We use a representation of nonnegative integers that is self delimiting and whose lexicographical ordering matches the ordering by value.  1 Introduction  Our motivation is a project in collaborative design for Civil Engineering being carried out at Stanford. The approach taken by the project, named CEDB (Collaborative Environment for the Design of Buildings) , leads to an interesting problem in version numbering. Our approa...
The TSIMMIS Approach to Mediation Data Models and Languages.
TSIMMIS --- The Stanford-IBM Manager of Multiple Information Sources --- is a system for integrating information. It offers a data model and a common query language that are designed to support the combining of information from many different sources. It also offers tools for generating automatically the components that are needed to build systems for integrating information. In this paper we shall discuss the principal architectural features and their rationale. 1. Introduction  In this first section we introduce the core concept of mediators, which the Tsimmis system implements. Section 2 discusses the components of Tsimmis, and Section 3 discusses the OEM data model used by Tsimmis. Section 4 introduces the mediator-specification language MSL, while in Section 5 we learn how it is used to generate mediators and other components automatically. Finally, in Section 6 we consider another language, LOREL, based on the OEM data model. It is the Tsimmis end-user&#039;s query language as well as...
Answering Queries Using Templates with Binding Patterns.
)  Anand Rajaraman Yehoshua Sagiv Jeffrey D. Ullman  Department of Computer Science Stanford University ABSTRACT  When integrating heterogeneous information resources, it is often the case that the source is rather limited in the kinds of queries it can answer. If a query is asked of the entire system, we have a new kind of optimization problem, in which we must try to express the given query in terms of the limited query templates that this source can answer. For the case of conjunctive queries, we show how to decide with a nondeterministic polynomial-time algorithm whether the given query can be answered. We then extend our results to allow arithmetic comparisons in the given query and in the templates.   I. Motivation  A data-integration system such as Tsimmis (Papakonstantinou, Garcia, and Widom [1994], Chawathe et al. [1994]) translates information sources of arbitrary type into a common data model and language. If a source is an SQL database, then its interface with the Tsimmis s...
Information Translation

The Role of Theory Today.

A survey of deductive database systems.
 
Argument Reduction by Factoring.
We identify a useful property of a program with re-spect to a predicate, called factoring. While we prove that detecting factorability is undecidable in general, we show that for a large class of programs, the pro-gram obtained by applying the Magic Sets transfor-mation is factorable with respect to the recursive predicate. When the factoring property holds, a sim-ple optimization of the program generated by the Magic Sets transformation results in a new program that is never less efficient than the Magic Sets pro-gram and is often dramatically more efficient, due to the reduction of the arity of the recursive predi-cate. We show that the concept of factoring general-izes some previously identified special cases of recur-sions, including separable recursions and right- and left-linear recursions, and that the specialized evalua-tion algorithms and rewriting strategies developed for
Validating Constraints with Partial Information Research Overview.
We are interested in the problem of validating the consistency of integrity constraints when data is modified. In particular, we consider how constraints can be checked with only &#034;partial information&#034;. Partial information may include: (1) the constraint specifications only, (2) the constraint specifications and the modified data, or (3) the constraint specifications, the modified data, and portions of the existing data. Methods for constraint checking with partial information can be much more efficient than traditional constraint checking methods (e.g. because work is done at compile time, or because less data is accessed). Partial information methods also enable constraint checking in scenarios where traditional constraint checking methods fail (e.g. in distributed environments where not all data is accessible). We explain how existing methods and results for query containment and for independence can be applied to problems (1) and (2) above, and we give an overview of our research in...
The TSIMMIS Project Integration of Heterogeneous Information Sources.
The goal of the Tsimmis Project is to develop tools that facilitate the rapid integration of heterogeneous information sources that may include both structured and unstructured data. This paper gives an overview of the project, describing components that extract properties from unstructured objects, that translate information into a common object model, that combine information from several sources, that allow browsing of information, and that manage constraints across heterogeneous sites. Tsimmis is a joint project between Stanford and the IBM Almaden Research Center.
Constraint Checking with Partial Information.
)  Ashish Gupta Yehoshua Sagivy Jeffrey D. Ullman Jennifer Widom  Dept. of Computer Science Stanford Univ., Stanford CA 94305  email: --agupta,sagiv,ullman,widom@cs.stanford.edu  contact phone: (415) 723--9745 FAX: (415) 725--7411  1. Introduction  The general problem we address is that of telling whether constraints remain satisfied as a database changes. Because checking a constraint on a database can be as complex as answering a query, it is desirable to minimize the work done in checking. As an extreme example, we would like to know when any update is guaranteed not to create a violation of a given constraint. In less extreme cases, we look for checks that can be done efficiently and that guarantee no violation occurs, even though sometimes a further, more expensive computation may be needed to check the constraint if the first test fails.  Constraints  A constraint is a query whose result is a 0-ary predicate that we call panic. If the query produces ; on a given database D, then ...
Efficient and Complete Tests for Database Integrity Constraint Checking.

Logical Query Optimization by Proff%2DTree Transformation.

New Frontiers in Database System Research.

The Interface Between Language Theory and Database Theory.

Generalizing Conjunctive Query Containment for View Maintenance and Integrity Constraint Verification %28Abstract%29.

A Comparison between Deductive and Object%2DOriented Database Systems.
The author will not pretend to be unbiased in the matter of comparing the deductive and object-oriented approaches to new database systems; he believes that despite some important concepts originating with the object-oriented approach, the deductive family of systems will ultimately dominate. We shall explore some of the reasons why the two approaches do not mix well. Fortunately, most of the features of object-oriented database systems can be incorporated in deductive systems (but not vice-versa). Then we argue that declarativeness is important for at least some of the new applications, and that declarative languages cannot be object-oriented in a nontrivial way. We next contrast the approaches with regard to the way they classify data elements. We close with an examination of the prospects for &#034;classless&#034; data, which is motivated by the prospect of databases where the number of distinct classes would be too large to name systematically. There are a number of challenges to implementin...
The Input%2FOutput Complexity of Transitive Closure.

Database Systems Achievements and Opportunities.

High%2DProbability Parallel Transitive%2DClosure Algorithms.

The Input%2FOutput Complexity of Transitive Closure.

High%2DProbability Parallel Transitive Closure Algorithms.

Selected Database Research at Stanford.

Database Systems Achievements and Opportunities %2D The %22Lagunita%22 Report of the NSF Invitational Workshop on the Future of Database System Research held in Palo Alto

Deductive Databases Achievements and Future Directions.
In the recent years, Deductive Databases have been the focus of intense research, which has brought dramatic advances in theory, systems and applications. A salient feature of deductive databases is their capability of supporting a declarative, rule-based style of expressing queries and applications on databases. As such, they find applications in disparate areas, such as knowledge mining from databases, and computer-aided design and manufacturing systems. In this paper, we briefly review the key concepts behind deductive databases and their newly developed enabling technology. Then, we describe current research on extending the functionality and usability of deductive databases and on providing a synthesis of deductive databases with procedural and object-oriented approaches. 1
Deductive Databases Achievements and Future Directions.
In the recent years, Deductive Databases have been the focus of intense research, which has brought dramatic advances in theory, systems and applications. A salient feature of deductive databases is their capability of supporting a declarative, rule-based style of expressing queries and applications on databases. As such, they find applications in disparate areas, such as knowledge mining from databases, and computer-aided design and manufacturing systems. In this paper, we briefly review the key concepts behind deductive databases and their newly developed enabling technology. Then, we describe current research on extending the functionality and usability of deductive databases and on providing a synthesis of deductive databases with procedural and object-oriented approaches. 1
Bottom%2DUp Beats Top%2DDown for Datalog.
Properties. In Luis Moniz Pereira and Anil Nerode, editors, Logic Programming and Non-Monotonic Reasoning, Proceedings of the Second International Workshop, pages 43--59. Lisbon, MIT Press, July 1993. [Min82] Jack Minker. On indefinite databases and the closed world assumption. In Proceedings of the 6th Conference on Automated Deduction, New York, pages 292--308. Springer, 1982. [Min88a] Jack Minker. Foundations of Deductive Databases. Morgan Kaufmann, 95 First Street, Los Altos, CA 94022, 1st edition, 1988. [Min88b] Jack Minker. Perspectives in deductive Databases. Journal of Logic Programming, 5:33--60, 1988. [Min89] Jack Minker. Toward a Foundation of Disjunctive Logic Programming. In Ewing L. Lusk and Ross A. Overbeek, editors, Proceedings of the North American Conference on Logic Programming, pages 1215--1235. MIT Press, 1989. [Min91] Jack Minker. An Overview of Nonmonotonic Reasoning and Logic Programming. CS-TR 2736, Computer Science Dept., Univ. Maryland, University of Marylan...
Principles of Database and Knowledge%2DBase Systems%2C Volume II

Bottom%2DUp Beats Top%2DDown for Datalog.
Properties. In Luis Moniz Pereira and Anil Nerode, editors, Logic Programming and Non-Monotonic Reasoning, Proceedings of the Second International Workshop, pages 43--59. Lisbon, MIT Press, July 1993. [Min82] Jack Minker. On indefinite databases and the closed world assumption. In Proceedings of the 6th Conference on Automated Deduction, New York, pages 292--308. Springer, 1982. [Min88a] Jack Minker. Foundations of Deductive Databases. Morgan Kaufmann, 95 First Street, Los Altos, CA 94022, 1st edition, 1988. [Min88b] Jack Minker. Perspectives in deductive Databases. Journal of Logic Programming, 5:33--60, 1988. [Min89] Jack Minker. Toward a Foundation of Disjunctive Logic Programming. In Ewing L. Lusk and Ross A. Overbeek, editors, Proceedings of the North American Conference on Logic Programming, pages 1215--1235. MIT Press, 1989. [Min91] Jack Minker. An Overview of Nonmonotonic Reasoning and Logic Programming. CS-TR 2736, Computer Science Dept., Univ. Maryland, University of Marylan...
Proof%2DTree Transformation Theorems and Their Applications.

Efficient Evaluation of Right%2D%2C Left%2D%2C and Mult%2DLineare Rules.

Argument Reduction by Factoring.
We identify a useful property of a program with re-spect to a predicate, called factoring. While we prove that detecting factorability is undecidable in general, we show that for a large class of programs, the pro-gram obtained by applying the Magic Sets transfor-mation is factorable with respect to the recursive predicate. When the factoring property holds, a sim-ple optimization of the program generated by the Magic Sets transformation results in a new program that is never less efficient than the Magic Sets pro-gram and is often dramatically more efficient, due to the reduction of the arity of the recursive predi-cate. We show that the concept of factoring general-izes some previously identified special cases of recur-sions, including separable recursions and right- and left-linear recursions, and that the specialized evalua-tion algorithms and rewriting strategies developed for
On the Convergence of Query Evaluation.

An Optimal Synchronizer for the Hypercube.

Principles of Database and Knowledge%2DBase Systems%2C Volume I
Modern database management systems essentially solve the problem of accessing and managing large volumes of related data on a single platform, or on a cluster of tightly­coupled platforms. But many problems remain when two or more databases need to work together. A fundamental problem is raised by semantic heterogeneity -- the fact that data du­ plicated across multiple databases is represented differently in the underlying database schemas. This tutorial describes fundamental problems raised by semantic heterogeneity and surveys theoretical frameworks that can provide solutions for them. The tutorial considers the following topics: (1) repre­ sentative architectures for supporting database interoperation; (2) notions for comparing the &#034;information capacity&#034; of database schemas; (3) providing support for read­only integrated views of data, including the virtual and materialized approaches; (4) providing support for read­write integrated views of data, including the issue of workflows on heterogeneous databases; and (5) research and tools for accessing and effectively using meta­data, e.g., to identify the relationships between schemas of different databases.
The Complexity of Ordering Subgoals.

Parallel Complexity of Logical Query Programs.

Efficient tests for top%2Ddown termination of logical rules.

An Optimal Synchronizer for the Hypercube.

Database Theory Past and Future.

Algorithms for the Compilation of Regular Expressions into PLAs.

YAWN%21 %28Yet Another Window on NAIL%21%29.

A Communication%2DTime Tradeoff.

Compilers Princiles%2C Techniques%2C and Tools.

Parallel Complexity of Logical Query Programs

Design Overview of the NAIL%21 System.
this paper, we have adopted the view of model-theoretic circumscription (cf. Etherington [15], Horty [22]) which is quite well-known in the literature [40] and we restrict interest only to Herbrand pre-interpretations. Notwithstanding the computational complexity of circumscription, algorithms still need to be developed to compute circumscription. It is often true that algorithms that have poor worst-case complexities may work well in practice. For example, experimental results indicate that our prototype implementations for linear programming based computations of monotonic databases [6], are more efficient in practice than Prolog. Precise details of the experiments may be found in [6]. In a similar vein, the precise efficiency of our techniques for computing circumscription can only be judged after implementing a prototype system and carrying out detailed experimentation with the implementation. We are currently developing such a prototype implementation for computing circumscription. The details of the implementation and experimental results reporting on the precise efficiency of our optimizations will be reported in Part II of this series of papers[13]. Preliminary experimental results indicate that (1) in Algorithm 1 and the analogous algorithms for computing parallel and prioritized circumscription, most of the time is spent around the first iteration of the loop, and (2) the compaction methods yield significant savings in time, and (3) a concept called &#034;locales&#034; for splitting the database into manageable chunks based on dependency analysis yields significant savings in the time required for compilation. However, these experimental results are still in a very preliminary stage, and we expect that it will be a few months before more reliable statistics are obtained...
Magic Sets and Other Strange Ways to Implement Logic Programs.
SLD resolution with negation as finite failure (SLDNF) reflects the procedural interpretation of predicate calculus as a programming language and forms the computational basis for Prolog systems. Despite its advantages for stack-based memory management, SLDNF is often not appropriate for query evaluation for three reasons: a) it may not terminate due to infinite positive recursion; b) it may not terminate due to infinite recursion through negation; c) it may repeatedly evaluate the same literal in a rule body, leading to unacceptable performance. We address three problems fir a goal-oriented query evaluation of general logic programs by presenting tabled evaluation with delaying (SLG resolution).
Convergence of Sideways Query Evaluation.

An Approach To Processing Queries In A Logic%2DBased Query Language.

Updating Logical Databases.
We suggest a new approach to database updates, in which a database is treated as a collection of theories. We investigate two issues: simultaneous multiple update operations and equivalence of databases under update operations. 1.
Logic and Database Systems.
. Recent work in query optimization has addressed the issue of placing expensive predicates in a query plan. In this paper we explore the predicate placement options considered in the Montage DBMS, presenting a family of algorithms that form successively more complex and effective optimization solutions. Through analysis and performance measurements of Montage SQL queries, we classify queries and highlight the simplest solution that will optimize each class correctly. We demonstrate limitations of previously published algorithms, and discuss the challenges and feasibility of implementing the various algorithms in a commercial-grade system.  1 Introduction  Relational Database Management Systems have begun to allow user-defined data types and operators to be utilized in ad-hoc queries. Simultaneously, ObjectOriented DBMSs have begun to offer ad-hoc query facilities, allowing declarative access to objects and methods that were previously only accessible through handcoded, imperative appl...
An Approach To Processing Queries In A Logic%2DBased Query Language.

A Communication%2DTime Tradeoff

Implementation of Logical Query Languages for Databases %28Abstract%29.

Implementation of Logical Query Languages for Databases.

Some Thoughts About Supercomputer Organization.

A Communication%2DTime Tradeoff

On the Equivalence of Logical Databases.

On Complementary and Independent Mappings on Databases.

Correcting Faults in Write%2DOnce Memory

On the Foundations of the Universal Relation Model.

System%2FU A Database System Based on the Universal Relation Assumption.

Flux%2C Sorting%2C and Supercomputer Organization for AI Applications.

Connections in Acyclic Hypergraphs.
It is well known that after placing n balls independently and uniformly at random into n bins, the fullest bin holds \Theta(log n= log log n) balls with high probability. Recently, Azar et al. analyzed the following: randomly choose d  bins for each ball, and then sequentially place each ball in the least full of its chosen bins [2]. They show that the fullest bin contains only log log n= log d + \Theta(1) balls with high probability. We explore extensions of this result to parallel and distributed settings. Our results focus on the tradeoff between the amount of communication and the final load. Given r rounds of communication, we provide lower bounds on the maximum load of \Omega\Gamma  r  p  log n= log log n) for a wide class of strategies. Our results extend to the case where the number of rounds is allowed to grow with n.  We then demonstrate parallelizations of the sequential strategy presented in Azar et al. that achieve loads within a constant factor of the lower bound for two ...
Data Structures and Algorithms.

Universal Relation Interfaces for Database Systems.

The Revenge of the JD.

On the Semantics of Updates in Databases.
We suggest here a methodology for updating data- The ability of the database user lo modify the con-bases with integrity constrain &amp; and rules for deriving inex- tent of the database, the so-called updale operation, is fun-plicit information. First we consider the problem of damental to all database management systems. Since updating arbitrary theories by inserting inu, them or delet- many users do not deal with the entire conceptual database
Fragments of Relations.
New application domains cause todays database sizes to grow rapidly, posing great demands on technology. Data fragmentation facilitates techniques (like distribution, parallelization, and main-memory computing) meeting these demands. Also, fragmentation might help improving e#cient processing of query types such as top N.  Database design and query optimization require a good notion of the costs resulting from a certain fragmentation. Our mathematically derived selectivity model facilitates this. Once its two parameters have been computed based on the fragmentation, after each (though usually infrequent) update, our model can forget the data distribution, resulting in fast and quite good selectivity estimation. We show experimental verification for Zipfian distributed IR databases.  Keywords: selectivity, fragmentation, Zipf, information retrieval, databases  1 Introduction  E#cient and e#ective processing of large amounts of data is of crucial importance in most computer applications,...
On Notions of Information Transfer in VLSI Circuits

Maximal Objects and the Semantics of Universal Relation Databases.

Corrigendum The Theory of Joins in Relational Databases.

On Kent%27s %22Consequences of Assuming a Universal Relation%22.
A universal algorithm for sequential data compression is presented. Its performance is investigated with respect to a nonprobabilistic model of constrained sources. The compression ratio achieved by the proposed universal code uniformly approaches the lower bounds on the compression ratios attainable by block-to-variable codes and variable-to-block codes designed to match a completely specified source.
Tools for Template Dependencies.

Principles of Database Systems%2C 2nd Edition

A Regular Expression Compiler.
We have developed Gigascope, a stream database for network applications including traffic analysis, intrusion detection, router configuration analysis, network research, network monitoring, and and performance monitoring and debugging. Gigascope is undergoing installation at many sites within the AT&amp;T network, including at OC48 routers, for detailed monitoring. In this paper we describe our motivation for and constraints in developing Gigascope, the Gigascope architecture and query language, and performance issues. We conclude with a discussion of stream database research problems we have found in our application. 1.
The U. R. Strikes Back.

Connections in Acyclic Hypergraphs.
It is well known that after placing n balls independently and uniformly at random into n bins, the fullest bin holds \Theta(log n= log log n) balls with high probability. Recently, Azar et al. analyzed the following: randomly choose d  bins for each ball, and then sequentially place each ball in the least full of its chosen bins [2]. They show that the fullest bin contains only log log n= log d + \Theta(1) balls with high probability. We explore extensions of this result to parallel and distributed settings. Our results focus on the tradeoff between the amount of communication and the final load. Given r rounds of communication, we provide lower bounds on the maximum load of \Omega\Gamma  r  p  log n= log log n) for a wide class of strategies. Our results extend to the case where the number of rounds is allowed to grow with n.  We then demonstrate parallelizations of the sequential strategy presented in Azar et al. that achieve loads within a constant factor of the lower bound for two ...
A Simplified Universal Relation Assumption and Its Properties.
One problem concerning the universal relation assumption is the inability of known methods to obtain a database scheme design in the general case, where the real-world constraints are given by a set of dependencies that includes embedded multivalued dependencies. We propose a simpler method of describing the real world, where constraints are given by functional dependencies and a single join dependency. The relationship between this method of defining the real world and the classical methods is exposed. We characterize in terms of hypergrapbs those multivalued dependencies that are the consequence of a given join dependency. Also characterized in terms of hypergraphs are those join dependencies that are equivalent to a set of multivalued dependencies.
Query Processing in Universal Relation Systems.

Template Dependencies A Large Class of Dependencies in Relational Databases and Its Complete Axiomatization.
 Analysis and Design of Relational Schemata for Database Systems. PhD thesis, UCLA, July 1976.  [Fagin 81] R. Fagin. A Normal Form for Relational Databases that is Based on Domains and Keys.  ACM Transactions on Database Systems, 6(3), September 1981. [Gadia 88] S.K. Gadia. A Homogeneous Relational Model and Query Languages for Temporal Databases. ACM Transactions on Database Systems, 13(4):418--448, December 1988. [Gadia 92] S.K. Gadia. A Seamless Generic Extension of SQL for Querying Temporal Data. Technical Report TR-92-02, Computer Science Department, Iowa State University, May 1992. [Jensen et al. 91] C. S. Jensen, L. Mark, and N. Roussopoulos. Incremental Implementation Model for Relational Databases with Transaction Time. IEEE Transactions on Knowledge and Data Engineering, 3(4):461--473, December 1991. [Jensen &amp; Snodgrass 92] C. S. Jensen and R. T. Snodgrass. Proposal of a Data Model for the Temporal Struc
The Compilation of Regular Expressions into Integrated Circuits.

The Theory of Functional and Template Dependencies.

A View of Directions in Relational Database Theory.

Optimal Wiring between Rectangles

Properties of Acyclic Database Schemes

Connections in Acyclic Hypergraphs.
It is well known that after placing n balls independently and uniformly at random into n bins, the fullest bin holds \Theta(log n= log log n) balls with high probability. Recently, Azar et al. analyzed the following: randomly choose d  bins for each ball, and then sequentially place each ball in the least full of its chosen bins [2]. They show that the fullest bin contains only log log n= log d + \Theta(1) balls with high probability. We explore extensions of this result to parallel and distributed settings. Our results focus on the tradeoff between the amount of communication and the final load. Given r rounds of communication, we provide lower bounds on the maximum load of \Omega\Gamma  r  p  log n= log log n) for a wide class of strategies. Our results extend to the case where the number of rounds is allowed to grow with n.  We then demonstrate parallelizations of the sequential strategy presented in Azar et al. that achieve loads within a constant factor of the lower bound for two ...
Fragments of Relations First Hack.

Equivalence of Relational Database Schemes.
Modern database management systems essentially solve the problem of accessing and managing large volumes of related data on a single platform, or on a cluster of tightly­coupled platforms. But many problems remain when two or more databases need to work together. A fundamental problem is raised by semantic heterogeneity -- the fact that data du­ plicated across multiple databases is represented differently in the underlying database schemas. This tutorial describes fundamental problems raised by semantic heterogeneity and surveys theoretical frameworks that can provide solutions for them. The tutorial considers the following topics: (1) repre­ sentative architectures for supporting database interoperation; (2) notions for comparing the &#034;information capacity&#034; of database schemas; (3) providing support for read­only integrated views of data, including the virtual and materialized approaches; (4) providing support for read­write integrated views of data, including the issue of workflows on heterogeneous databases; and (5) research and tools for accessing and effectively using meta­data, e.g., to identify the relationships between schemas of different databases.
Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions.

Deadlock%2DFree Packet Switching Networks.
Abstract. Deadlocks are very serious system failures and have been observed in existing packet switching networks (PSN’s). Several problems related to the design of deadlock-free PSN’s are investigated here. Polynomial-time algorithms are given for some of these problems, but most of them are shown to be NP-complete or NP-hard, and therefore polynomial-time algorithms are not likely to be found. Key words, packet switching network, deadlock, complexity, NP-complete, flow control, routing, computer network, communication network 1. Basic definitions. A packet switching network (or PSN) is a directed graph G (V, E); the vertices V represent processors, and the edgesE represent communication links.We assume messages, called packets, are to be passed between processors. Each vertex vi has an associated constant bi, the number of buffers at this vertex; a buffer can hold exactly one packet. Associated with each packet is an acyclic route /-)1, V2, &#034; Vq, which is a path in G. Vertex /)1 is the source, and vq is the destination vertex for the packet.We assume afixedroutingprocedure [KL],where apacket’s route is determined at the source node. We may also assume that the route of a packet is included as part of the message in the packet, although in practice the packet could
Principles of Database Systems%2C 1st Edition

The Compilation of Regular Expressions into Integrated Circuits %28Extended Abstract%29

The Interaction between Functional Dependencies and Template Dependencies.
Abstract. This paper discusses algorithms for topic selection queries, designed to query a database containing metadata about web information resources. The metadata database contains topics and relationships, called metalinks, about topics. Topics in the database contain associated importance scores. The topic selection operator TSelection selects, within time T, topics that satisfy a given selection formula and having output importance scores above a given threshold value or in the top-k. The selection formula contains expensive predicates, in the form of user-defined functions. To minimize the number of expensive predicate evaluations (probes) in the TSelection algorithm, we introduce and evaluate three heuristics. Also, due to the time constraint T, the TSelection algorithm may terminate without locating all output tuples. In order to maximize the number of output tuples found, we introduce and evaluate three heuristics to locate a tuple to evaluate at a given time. 1
A Complete Axiomatization for a Large Class of Dependencies in Relational Databases

System%2FU A Database System Based on the Universal Relation Assumption.

System%2FU A Database System Based on the Universal Relation Assumption.

Universal Instances.

A Scheme for the Automatic Inference of Variable Types.

Adequacy of Decompositions of Relational Databases.

Introduction to Automata Theory%2C Languages and Computation.

Adequacy of Decompositions of Relational Databases.

Modeling Communications Protocols by Automata

The Universality of Data Retrieval Languages.
Many structural analyses of software systems are naturally formalized as relational queries, for example, the detection of design patterns, patterns of problematic design, code clones, dead code, and di#erences between the as-built and the as-designed architecture. This paper describes CrocoPat, an application-independent tool for relational programming. Through its e#ciency and its expressive language, CrocoPat enables practically important analyses of real-world software systems that are not possible with other graph analysis tools, in particular analyses that involve transitive closures and the detection of patterns in graphs. The language is easy to use, because it is based on the well-known first-order predicate logic. The tool is easy to integrate into other software systems, because it is a small command-line tool that uses a simple text format for input and output of relations.
Equivalence of Relational Database Schemes
Modern database management systems essentially solve the problem of accessing and managing large volumes of related data on a single platform, or on a cluster of tightly­coupled platforms. But many problems remain when two or more databases need to work together. A fundamental problem is raised by semantic heterogeneity -- the fact that data du­ plicated across multiple databases is represented differently in the underlying database schemas. This tutorial describes fundamental problems raised by semantic heterogeneity and surveys theoretical frameworks that can provide solutions for them. The tutorial considers the following topics: (1) repre­ sentative architectures for supporting database interoperation; (2) notions for comparing the &#034;information capacity&#034; of database schemas; (3) providing support for read­only integrated views of data, including the virtual and materialized approaches; (4) providing support for read­write integrated views of data, including the issue of workflows on heterogeneous databases; and (5) research and tools for accessing and effectively using meta­data, e.g., to identify the relationships between schemas of different databases.
Deadlock%2DFree Packet Switching Networks
Abstract. Deadlocks are very serious system failures and have been observed in existing packet switching networks (PSN’s). Several problems related to the design of deadlock-free PSN’s are investigated here. Polynomial-time algorithms are given for some of these problems, but most of them are shown to be NP-complete or NP-hard, and therefore polynomial-time algorithms are not likely to be found. Key words, packet switching network, deadlock, complexity, NP-complete, flow control, routing, computer network, communication network 1. Basic definitions. A packet switching network (or PSN) is a directed graph G (V, E); the vertices V represent processors, and the edgesE represent communication links.We assume messages, called packets, are to be passed between processors. Each vertex vi has an associated constant bi, the number of buffers at this vertex; a buffer can hold exactly one packet. Associated with each packet is an acyclic route /-)1, V2, &#034; Vq, which is a path in G. Vertex /)1 is the source, and vq is the destination vertex for the packet.We assume afixedroutingprocedure [KL],where apacket’s route is determined at the source node. We may also assume that the route of a packet is included as part of the message in the packet, although in practice the packet could
Optimal Partial%2DMatch Retrieval When Fields Are Independently Specified.

The Theory of Joins in Relational Databases.

Efficient Optimization of a Class of Relational Expressions.

Equivalences Among Relational Expressions.
We present Structural Logistic Regression, an extension of logistic  regression to modeling relational data. It is an integrated approach to building  regression models from data stored in relational databases in which potential predictors,  both boolean and real-valued, are generated by structured search in the  space of queries to the database, and then tested with statistical information criteria  for inclusion in a logistic regression. Using statistics and relational representation  allows modeling in noisy domains with complex structure. Link prediction  is a task of high interest with exactly such characteristics. Be it in the domain  of scientific citations, social networks or hypertext, the underlying data are extremely  noisy and the features useful for prediction are not readily available in a  &#034;flat&#034; file format. We propose the application of Structural Logistic Regression to  building link prediction models, and present experimental results for the task of  predicting citations made in scientific literature using relational data taken from  the CiteSeer search engine. This data includes the citation graph, authorship and  publication venues of papers, as well as their word content.
Crossfertilization Of DBMS Research With Other Disciplines Of Computer Science %28Panel Discussion%29.

A General Scheme for the Automatic Inference of Variable Types.

Efficient Optimization of a Class of Relational Expressions %28Abstract%29.

The Theory of Joins in Relational Data Bases %28Extended Abstract%29

Code Generation for Machines with Multiregister Operations.
Entity resolution has received considerable attention in recent years. Given many references to underlying entities, the goal is to predict which references correspond to the same entity. We show how to extend the Latent Dirichlet Allocation model for this task and propose a probabilistic model for collective entity resolution for relational domains where references are connected to each other. Our approach differs from other recently proposed entity resolution approaches in that it is a) generative, b) does not make pair-wise decisions and c) captures relations between entities through a hidden group variable. We propose a novel sampling algorithm for collective entity resolution which is unsupervised and also takes entity relations into account. Additionally, we do not assume the domain of entities to be known and show how to infer the number of entities from the data. We demonstrate the utility and practicality of our relational entity resolution approach for author resolution in two real-world bibliographic datasets. In addition, we present preliminary results on characterizing conditions under which relational information is useful. 
A Model of Statistical Databases and Their Security.

Monotone Data Flow Analysis Frameworks.

Operations on Sparse Relations.

Code Generation for Expressions with Common Subexpressions.

Finding the Depth of a Flow Graph.

Evaluating Relational Expressions with Dense and Sparse Arguments.

Economy of Description by Parsers%2C DPDA%27S%2C and PDA%27S.

Induction Variables in Very High Level Languages.

Code Generation for Expressions with Common Subexpressions.

Finding the Depth of a Flow Graph

Protection in Operating Systems.
Existing mandatory access control systems for operating systems are difficult to use. We identify several principles for designing usable access control systems and introduce the Usable Mandatory Integrity Protection (UMIP) model that adds usable mandatory access control to operating systems. The UMIP model is designed to preserve system integrity in the face of network-based attacks. The usability goals for UMIP are twofold. First, configuring a UMIP system should not be more difficult than installing and configuring an operating system. Second, existing applications and common usage practices can still be used under UMIP. UMIP has several novel features to achieve these goals. For example, it introduces several concepts for expressing partial trust in programs. Furthermore, it leverages information in the existing discretionary access control mechanism to derive file labels for mandatory integrity protection. We also discuss our implementation of the UMIP model for Linux using the Linux Security Modules framework, and show that it is simple to configure, has low overhead, and effectively defends against a number of network-based attacks. 
Bounds on the Complexity of the Longest Common Subsequence Problem.
A brief survey of the theory and practice of sequence comparison is made focusing on diff, the UNIX  1  file difference utility. 1 Sequence comparison  Sequence comparison is a deep and fascinating subject in Computer Science, both theoretical and practical. However, in our opinion, neither the theoretical nor the practical aspects of the problem are well understood and we feel that their mastery is a true challenge for Computer Science. The central problem can be stated very easily: find an algorithm, as efficient and practical as possible, to compute a longest common subsequence (lcs for short) of two given sequences  2  . As usual, a subsequence of a sequence is another sequence obtained from it by deleting some (not necessarily contiguous) terms. Thus, both en/pri  and en/pai are longest common subsequences of sequence/comparison and  theory/and/practice.   Part of this work was done while the author was visiting the Universit&#039;e de Rouen, in 1987. That visit was partially supported...
Global Data Flow Analysis and Iterative Algorithms.
ABSTRACT Kildall has developed data propagation algorithms for code optimization m a general lattice theoretic framework. In another directmn, Hecht and Ullman gave a strong upper bound on the number of iterations required for propagation algorithms when the data is represented by bit vectors and depth-first ordering of the flow graph is used The present paper combines the ideas of these two papers by considering conditions under whmh the bound of Hecht and Ullman applies to the depth-first veremn of Klldall&#039;s general data propagation algorithm. It is shown that the following condition is necessary and sufficient Let f and g be any two functions which could be associated with blocks of a flow graph, let x be an arbitrary lattice element, and let 0 be the lattice zero Then (*) (Vf,g,x) [fg(0)&gt; g(0)A f(x) / ~ x] Then it is shown that several of the particular instances of the techniques Kildall found useful do not meet condition (*)
Node Listings for Reducible Flow Graphs.

On Finding Lowest Common Ancestors in Trees.
. This paper gives a CREW PRAM algorithm for the problem of finding lowest common ancestors in a forest under the insertion of leaves and roots and the deletion of leaves. For a forest with a maximum of n vertices, the algorithm takes O(m=p+r log p+min(m; r log n)) time and O(n) space using p processors to process a sequence of m operations that are presented over r rounds. Furthermore, lowest common ancestor queries can be done in worst case constant time using a single processor. For one processor, the algorithm matches the bounds achieved by the best sequential algorithm known. The new algorithm is somewhat simpler and has smaller constants in the time and space complexity.  1 Introduction  Finding lowest common ancestors in trees is a frequently occurring problem in the literature and has found application in such diverse problems as computing dominators in reducible flow graphs [1], detecting negative cycles in sparse graphs [12], planarity testing [9], and computing weighted matc...
Economy of Descriptions by Parsers%2C DPDA%27s%2C and PDA%27s

Evaluating Relational Expressions with Dense and Sparse Arguments

Application of Lattice Algebra to Loop Optimization.

On the Complexity of LR%28k%29 Testing.

On Protection in Operating System.
Existing mandatory access control systems for operating systems are difficult to use. We identify several principles for designing usable access control systems and introduce the Usable Mandatory Integrity Protection (UMIP) model that adds usable mandatory access control to operating systems. The UMIP model is designed to preserve system integrity in the face of network-based attacks. The usability goals for UMIP are twofold. First, configuring a UMIP system should not be more difficult than installing and configuring an operating system. Second, existing applications and common usage practices can still be used under UMIP. UMIP has several novel features to achieve these goals. For example, it introduces several concepts for expressing partial trust in programs. Furthermore, it leverages information in the existing discretionary access control mechanism to derive file labels for mandatory integrity protection. We also discuss our implementation of the UMIP model for Linux using the Linux Security Modules framework, and show that it is simple to configure, has low overhead, and effectively defends against a number of network-based attacks. 
Node Listings for Reducible Flow Graphs

On the Complexity of LR%28k%29 Testing.

Deterministic Parsing of Ambiguous Grammars.
Entity resolution has received considerable attention in recent years. Given many references to underlying entities, the goal is to predict which references correspond to the same entity. We show how to extend the Latent Dirichlet Allocation model for this task and propose a probabilistic model for collective entity resolution for relational domains where references are connected to each other. Our approach differs from other recently proposed entity resolution approaches in that it is a) generative, b) does not make pair-wise decisions and c) captures relations between entities through a hidden group variable. We propose a novel sampling algorithm for collective entity resolution which is unsupervised and also takes entity relations into account. Additionally, we do not assume the domain of entities to be known and show how to infer the number of entities from the data. We demonstrate the utility and practicality of our relational entity resolution approach for author resolution in two real-world bibliographic datasets. In addition, we present preliminary results on characterizing conditions under which relational information is useful. 
NP%2DComplete Scheduling Problems.
This paper presents the development and simulation of a novel Genetic Algorithm (GA) based methodology applied to optimal tuning of a fuzzy dispatching system for a fleet of automated guided vehicles in a flexible manufacturing environment. The dispatching rules are further transformed into a continuously adaptive procedure to capitalize the online information available from a shop floor at all times. The entire problem is simulated using MATLAB/SIMULINK. The simulation results obtained show that GA is an efficient and effective tool to achieve optimal performance for the well-known NP-complete scheduling problem.
A Simple Algorithm for Global Data Flow Analysis Problems.

Evaluating Polynomials at Fixed Sets of Points.

The Design and Analysis of Computer Algorithms.

Bounds on the Complexity of the Longest Common Subsequence Problem %28Extended Abstract%29

Operations on Sparse Relations and Efficient Algorithms for Grammar Problems %28Extended Abstract%29

Characterizations of Reducible Flow Graphs.

Worst%2DCase Performance Bounds for Simple One%2DDimensional Packing Algorithms.
Abstract. The following abstract problem models several practical problems in computer science and operations research: given a list L of real numbers between 0 and 1, place the elements ofL into a minimum number L * of &amp;quot;bins &amp;quot; so that no bin contains numbers whose sum exceeds 1. Motivated by the likelihood that an excessive amount of computation will be required by any algorithm which actually determines an optimal placement, we examine the performance of a number of simple algorithms which obtain &amp;quot;good &amp;quot; placements. The first-fit algarithm places each number, in succession, into the first bin inwhich it fits.The best-fitalgorithm placeseachnumber, in succession, into themostnearly full bin in which it fits. We show that neither the first-fit nor the best-fit algorithm will ever use more than 17. a-6. + 2 bins. Furthermore, we outline a proof that, if L is in decreasing order, then neither algorithm will use more thanL * + 4 bins. Examples are given to show that both upper bounds are essentially the best possible. Similar results are obtained when the list L contains no numbers larger than &lt; 1. 1. Introduction. Recent results in complexity theory 3], [10] indicate that many combinatorial optimization problemsmay be effectively impossible to solve,
Deterministic Parsing of Ambiguous Grammars.
Entity resolution has received considerable attention in recent years. Given many references to underlying entities, the goal is to predict which references correspond to the same entity. We show how to extend the Latent Dirichlet Allocation model for this task and propose a probabilistic model for collective entity resolution for relational domains where references are connected to each other. Our approach differs from other recently proposed entity resolution approaches in that it is a) generative, b) does not make pair-wise decisions and c) captures relations between entities through a hidden group variable. We propose a novel sampling algorithm for collective entity resolution which is unsupervised and also takes entity relations into account. Additionally, we do not assume the domain of entities to be known and show how to infer the number of entities from the data. We demonstrate the utility and practicality of our relational entity resolution approach for author resolution in two real-world bibliographic datasets. In addition, we present preliminary results on characterizing conditions under which relational information is useful. 
Analysis of a Simple Algorithm for Global Flow Problems.

Polynomial Complete Scheduling Problems.

On Finding Lowest Common Ancestors in Trees
. This paper gives a CREW PRAM algorithm for the problem of finding lowest common ancestors in a forest under the insertion of leaves and roots and the deletion of leaves. For a forest with a maximum of n vertices, the algorithm takes O(m=p+r log p+min(m; r log n)) time and O(n) space using p processors to process a sequence of m operations that are presented over r rounds. Furthermore, lowest common ancestor queries can be done in worst case constant time using a single processor. For one processor, the algorithm matches the bounds achieved by the best sequential algorithm known. The new algorithm is somewhat simpler and has smaller constants in the time and space complexity.  1 Introduction  Finding lowest common ancestors in trees is a frequently occurring problem in the literature and has found application in such diverse problems as computing dominators in reducible flow graphs [1], detecting negative cycles in sparse graphs [12], planarity testing [9], and computing weighted matc...
Fast Algorithms for the Elimination of Common Subexpressions

Parsing Algorithms with Backtrack
This paper proposes an efficient linguistic processing strategy for speech recognition and understanding using a dependency structure grammar. The strategy includes parsingand phrase prediction algorithms. After speech processing and phrase recognition based on phoneme recognition, the parser extracts the sentence with the best likelihood taking account of the phonetic likelihood of phrase candidates and the linguistic likelihood of the semantic inter-phrase dependency relationships. A fast parsing algorithm using breadth-first search is also proposed. The predictor pre-selects the pt.ase candidates using transition rules combined with a dependency structure to reduce the amount of phonetic processing. The proposed linguistic processor has been tested through speech recognition experiments. The experimental results show that it greatly increases the accuracy of speech recognitions, and the breadth-first parsing algorithm and predictor increase processing speed
Error Detection in Precedence Parsers.

A Technique for Speeding up LR%28k%29 Parsers.

Set Merging Algorithms.
This paper presents an implemented computational  model of lexical development for the case of action verbs.  A simulated agent is trained by an informant giving  labels to the agent&#039;s actions (here hand motions) and  the system learns to both label and carry out similar  actions. Computationally, the system employs a novel  form of active representation and is explicitly intended  to be neurally plausible. The learning methodology is a  version of Bayesian model merging (Omohundro, 1992).  The verb learning model is placed in the broader context  of the L0 project on embodied natural language and its  acquisition.  
A Fast Algorithm for the Elimination of Common Subexpressions

Worst%2DCase Analysis of Memory Allocation Algorithms
 
Flow Graph Reducibility
Abstract — Many common iterative or recursive DSP applications can be represented by synchronous data-flow graphs (SDFGs). A great deal of research has been done attempting to optimize such applications through retiming. However, despite its proven effectiveness in transforming single-rate data-flow graphs to equivalent DFGs with smaller clock periods, the use of retiming for attempting to reduce the execution time of synchronous DFGs has never been explored. In this paper, we do just this. We develop the basic definitions and results necessary for expressing and studying SDFGs. We review the problems faced when attempting to retime a SDFG in order to minimize clock period, then present algorithms for doing this. Finally, we demonstrate the effectiveness of our methods on several examples. I.
A Technique for Speeding Up LR%28k%29 Parsers

Weak and Mixed Strategy Precedence Parsing.

A Note on the Efficiency of Hashing Functions.

Equivalence of Programs with Structured Variables.

Optimization of LR%28k%29 Parsers.
and siblings (James Jr., Jacqueline, and Josephine) throughout my education, without whose support I would never have persevered. I thank Professor Hank Dietz, my advisor, for his encouragement and tolerance over the past five years during my Masters and Doctorate. I thank Professor Russell Quong for his interest in my research and helping me develop many of the advanced language and parsing ideas in the ANTLR parser generator. I wish to acknowledge Professors Dave Meyer and Jose Fortes for getting me interested in electrical engineering and encouraging me to attend graduate school. Professor Leah Jamieson deserves thanks for taking a chance on me and supporting my continued studies at Purdue. I thank Professors Matt O’Keefe and Paul Woodward at the University of Minnesota for providing me with the fellowship to finish my studies. Further, I wish to thank Paul Woodward for giving me the work ‘‘ack.’ ’ I acknowledge Kevin Edgar for whom ‘‘no thanks is too much.’’ To the users of the Purdue Compiler-Construction Tool Set and codeveloper, Will Cohen, I
Optimization of Straight Line Programs.

The Transitive Reduction of a Directed Graph.
Modern enterprises increasingly use the workflow paradigm to prescribe how business processes should be performed. Processes are typically modeled as annotated activity graphs. We present an approach for a system that constructs process models from logs of past, unstructured executions of the given process. The graph so produced conforms to the dependencies and past executions present in the log. By providing models that capture the previous executions of the process, this technique allows easier introduction of a workflow system and evaluation and evolution of existing process models. We also present results from applying the algorithm to synthetic data sets as well as process logs obtained from an IBM Flowmark installation.
Flow Graph Reducibility.
Abstract — Many common iterative or recursive DSP applications can be represented by synchronous data-flow graphs (SDFGs). A great deal of research has been done attempting to optimize such applications through retiming. However, despite its proven effectiveness in transforming single-rate data-flow graphs to equivalent DFGs with smaller clock periods, the use of retiming for attempting to reduce the execution time of synchronous DFGs has never been explored. In this paper, we do just this. We develop the basic definitions and results necessary for expressing and studying SDFGs. We review the problems faced when attempting to retime a SDFG in order to minimize clock period, then present algorithms for doing this. Finally, we demonstrate the effectiveness of our methods on several examples. I.
The Care and Feeding of LR%28k%29 Grammars

Translations on a Context%2DFree Grammar

Principles of Optimal Page Replacement.

Characterizations and Extensions of Pushdown Translations.

Parsing Algorithms with Backtrack
This paper proposes an efficient linguistic processing strategy for speech recognition and understanding using a dependency structure grammar. The strategy includes parsingand phrase prediction algorithms. After speech processing and phrase recognition based on phoneme recognition, the parser extracts the sentence with the best likelihood taking account of the phonetic likelihood of phrase candidates and the linguistic likelihood of the semantic inter-phrase dependency relationships. A fast parsing algorithm using breadth-first search is also proposed. The predictor pre-selects the pt.ase candidates using transition rules combined with a dependency structure to reduce the amount of phonetic processing. The proposed linguistic processor has been tested through speech recognition experiments. The experimental results show that it greatly increases the accuracy of speech recognitions, and the breadth-first parsing algorithm and predictor increase processing speed
Equivalence of Programs with Structured Variables

Transformations on Straight Line Programs%2DPreliminary Version

The Generation of Optimal Code for Arithmetic Expressions.
Computer programs are portable to the extent that they can be moved to new computing environments with much less effort than it would take to rewrite them. In the limit, a program is perfectly portable if it can be moved at will with no change whatsoever. Recent C language extensions have made it easier to write portable programs. Some tools have also been developed that aid in the detection of nonportable constructions. With these tools many programs have been moved from the PDP-11 on which they were developed to other machines. In particular, the UNIX � operating system and most of its software have been transported to the Interdata 8/32. The source-language representation of most of the code involved is identical in all environments. I.
On the Computational Power of Pushdown Automata.

A Characterization of Two%2DWay Deterministic Classes of Languages.

A Characterization of Two%2DWay Deterministic Classes of Languages

Translations on a Context Free Grammar

Some Results on Tape%2DBounded Turing Machines.

Halting Stack Automata.

Syntax Directed Translations and the Pushdown Assembler.
different communities working in the rapidly growing field of statistical, tree-structured models of
Properties of Syntax Directed Translations.
The concept of macro tree transducer is a formal model for studying properties of syntax-- directed translations and of functional languages which are based on primitive recursion. In this paper, for output languages of producing and nondeleting macro tree transducers, we introduce and prove a pumping lemma. We apply this pumping lemma to gain two results: (1) there is no producing and nondeleting macro tree transducer which computes the set of all monadic trees with double exponential height as output and (2) there are hierarchies of producing and nondeleting macro tree transducers with respect to their number of functions.  
A General Theory of Translation.
In order to define the semantics of diagram languages, new techniques  may be developed following the established approaches of denotational,  operational, or algebraic semantics of programming languages. Due to the  multi-dimensional nature of diagrams (as opposed to the linear structure of  programs), these new approaches should be based on graphs (rather than  trees or terms) and graph transformation could provide the underlying technology.  In this paper, we try to substantiate this claim by reviewing some of the  most important approaches to semantics and discussing their applicability to  diagram languages.  Keywords  diagram languages, semantics, graph transformation  1 Introduction  The most important means for communication is the use of language. The language can be a natural one - like in human-human communication - or an artificial  one - as in human-computer or computer-computer communication.  In general, in the case of speaking, writing, or reading, the symbols in the la...
Automaton Analogs of Syntax Directed Translation Schemata

Universal Two State Machines Characterization Theorems and Decomposition Schemes

Sets Accepted by One%2DWay Stack Automata Are Context Sensitive

Time and Tape Complexity of Pushdown Automaton Languages

Decidable and Undecidable Questions About Automata.

Relations Between Time and Tape Complexities.

Deterministic Stack Automata and the Quotient Operator.

The Theory of Languages.
We study the randomized version of a computation model (introduced in [9, 10]) that restricts random access to external memory and internal memory space. Essentially, this model can be viewed as a powerful version of a data stream model that puts no cost on sequential scans of external memory (as other models for data streams) and, in addition, (like other external memory models, but unlike streaming models), admits several large external memory devices that can be read and written to in parallel. We obtain tight lower bounds for the decision problems set equality, multiset equality, and checksort. More precisely, we show that any randomized one-sided-error bounded Monte Carlo algorithm for these problems must perform Ω(logN) random accesses to external memory devices, provided that the internal memory size is at most O ( 4 √ N/logN), where N denotes the size of the input data. From the lower bound on the set equality problem we can infer lower bounds on the worst case data complexity of query evaluation for the languages XQuery, XPath, and relational algebra on streaming data. More precisely, we show that there exist queries in XQuery, XPath, and relational algebra, such that any (randomized) Las Vegas algorithm that evaluates these queries must perform Ω(logN) random accesses to external memory devices, provided that the internal memory size is at most O ( 4 √ N/logN).
An Approach to a Unified Theory of Automata

Two Results on One%2DWay Stack Automata

Nonerasing Stack Automata.

